package MonotonicStack;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author Lzm
 * @version 1.0
 */
public class nextGreaterElement_ {
  @Test
  public void nextGreaterElementTest(){
    int[] nums1 = new int[]{4,1,2};
    int[] nums2 = new int[]{1,3,4,2};
    nextGreaterElement(nums1,nums2);
  }


  public int[] nextGreaterElement(int[] nums1, int[] nums2) {
    Map<Integer,Integer> map = new HashMap<>();
    Stack<Integer> stack = new Stack<>();
    int[] result = new int[nums1.length];
    Arrays.fill(result,-1);
    //将nums2的元素作为k, 下标作为v
    for (int i = 0 ; i < nums1.length ; i++){
      map.put(nums1[i], i);
    }
    stack.push(0);
    for (int i = 1 ; i < nums2.length ; i++){
      // 遍历nums2, 找出比当前元素大的右边元素
      while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
        if (map.containsKey(nums2[stack.peek()])){
          result[map.get(nums2[stack.peek()])] = nums2[i];
        }
        stack.pop();
      }
    }
    return result;
  }
}
